package sort

import (
	"fmt"
	"math/rand"
	"sort"
)

func BubbleSort(arr []int) {
	for i := 0; i < len(arr)-1; i++ {
		for j := 0; j < len(arr)-i-1; j++ {
			if arr[j] > arr[j+1] {
				arr[j], arr[j+1] = arr[j+1], arr[j]
			}
		}
	}
}

func SelectionSort(arr []int) {
	for i := 0; i < len(arr)-1; i++ {
		loc := i
		for j := i; j < len(arr); j++ {
			if arr[j] < arr[loc] {
				loc = j
			}
		}
		arr[loc], arr[i] = arr[i], arr[loc]
	}
}

func InsertionSort(arr []int) {
	for i := 1; i < len(arr); i++ {
		j := i - 1
		tmp := arr[i]
		for ; j >= 0; j-- {
			if arr[j] > tmp {
				arr[j+1] = arr[j]
			} else {
				arr[j+1] = tmp
				break
			}
		}
	}
}

func _QuickSort(arr []int, left, right int) {
	if left < right {
		partitionIdx := partition(arr, left, right)
		_QuickSort(arr, left, partitionIdx-1)
		_QuickSort(arr, partitionIdx+1, right)
	}
}

func partition(arr []int, left, right int) int {
	pivot := left
	index := left + 1
	for i := index; i <= right; i++ {
		if arr[i] < arr[pivot] {
			arr[i], arr[index] = arr[index], arr[i]
			index++
		}
	}
	arr[pivot], arr[index-1] = arr[index-1], arr[pivot]
	return index - 1
}

func QuickSort(arr []int) {
	_QuickSort(arr, 0, len(arr)-1)
}

func merge(arr []int, left, right, middle int) {
	tmp := make([]int, right-left+1)
	locLeft, locRight := left, middle+1

	for i := 0; i < len(tmp); i++ {
		if locLeft > middle {
			tmp[i] = arr[locRight]
			locRight++
		} else if locRight > right {
			tmp[i] = arr[locLeft]
			locLeft++
		} else {
			if arr[locLeft] < arr[locRight] {
				tmp[i] = arr[locLeft]
				locLeft++
			} else {
				tmp[i] = arr[locRight]
				locRight++
			}
		}
	}
	for i := 0; i < len(tmp); i++ {
		arr[left+i] = tmp[i]
	}
}

func _MergeSort(arr []int, left, right int) {
	if left < right {
		middle := (left + right) / 2
		_MergeSort(arr, left, middle)
		_MergeSort(arr, middle+1, right)
		merge(arr, left, right, middle)
	}
}

func MergeSort(arr []int) {
	_MergeSort(arr, 0, len(arr)-1)
}

func heapify(arr []int, arrLen, i int) {
	largest := i
	l := 2*i + 1
	r := 2*i + 2
	if l < arrLen && arr[l] > arr[largest] {
		largest = l
	}
	if r < arrLen && arr[r] > arr[largest] {
		largest = r
	}
	if largest != i {
		arr[i], arr[largest] = arr[largest], arr[i]
		heapify(arr, arrLen, largest)
	}
}
func buildMaxHeap(arr []int) {
	arrLen := len(arr)
	for i := arrLen/2 - 1; i >= 0; i-- {
		heapify(arr, arrLen, i)
	}
}

func HeapSort(arr []int) {
	arrLen := len(arr)
	buildMaxHeap(arr)
	for i := arrLen - 1; i >= 0; i-- {
		arr[0], arr[i] = arr[i], arr[0]
		heapify(arr, i, 0)
	}
}

func ShellSort(arr []int) {
	arrLen := len(arr)
	gap := 1
	for gap < arrLen/3 {
		gap = 3*gap + 1
	}
	for gap > 0 {
		for i := gap; i < arrLen; i++ {
			temp := arr[i]
			j := i - gap
			for j >= 0 && arr[j] > temp {
				arr[j+gap] = arr[j]
				j -= gap
			}
			arr[j+gap] = temp
		}
		gap /= 3
	}
}

func CountingSort(arr []int) {
	count := make([]int, 100)
	for i := 0; i < len(arr); i++ {
		count[arr[i]]++
	}
	loc := 0
	for i := 0; i < 100; i++ {
		for j := 0; j < count[i]; j++ {
			arr[loc] = i
			loc++
		}
	}
}

func RadixSort(arr []int) {
	// 获取最大位数
	maxData := arr[0]
	for i := 1; i < len(arr); i++ {
		if arr[i] > maxData {
			maxData = arr[i]
		}
	}
	dev := 1
	mod := 10
	for maxData >= mod {
		maxData /= 10
		dev++
	}
	// 分配桶

	mod = 1
	for i := 0; i < dev; i++ {
		var buckets [10][]int
		for j := 0; j < len(arr); j++ {
			buckets[(arr[j]/mod)%10] = append(buckets[(arr[j]/mod)%10], arr[j])
		}
		mod *= 10
		// 收集
		loc := 0
		for j := 0; j < 10; j++ {
			for _, v := range buckets[j] {
				arr[loc] = v
				loc++
			}
		}
	}
}

func BucketSort(arr []int) {
	if len(arr) <= 1 {
		return
	}
	maxVar := arr[0]
	minVar := arr[0]
	for i := 0; i < len(arr); i++ {
		if arr[i] > maxVar {
			maxVar = arr[i]
		}
		if arr[i] < minVar {
			minVar = arr[i]
		}
	}
	bucketSize := 5
	bucketNum := (maxVar-minVar)/bucketSize + 1
	buckets := make([][]int, bucketNum)
	for i := 0; i < len(arr); i++ {
		buckets[(arr[i]-minVar)/bucketSize] = append(buckets[(arr[i]-minVar)/bucketSize], arr[i])
	}
	index := 0
	for i := 0; i < len(buckets); i++ {
		InsertionSort(buckets[i])
		for j := 0; j < len(buckets[i]); j++ {
			arr[index] = buckets[i][j]
			index++
		}
	}
}

func judgeSort(arr []int) bool {
	// 计算现有结果
	temp := make([]int, len(arr))
	copy(temp, arr)
	sort.Ints(temp)
	for i := 0; i < len(arr); i++ {
		if temp[i] != arr[i] {
			fmt.Println("Sort Err")
			for j := 0; j < len(arr); j++ {
				fmt.Print(arr[i], " ")
			}
			return false
		}
	}
	return true
}
func Sort() {
	// 随机生成40个100以内的整数
	originArr := make([]int, 40)
	// 拷贝构造arr
	arr := make([]int, 40)
	for i := 0; i < 40; i++ {
		originArr[i] = rand.Intn(100)
		fmt.Printf("%d ", originArr[i])
	}
	fmt.Println()
	copy(arr, originArr)
	// 排序,传入拷贝
	BubbleSort(arr)
	if judgeSort(arr) {
		fmt.Println("Bubble Sort Success")
	}
	copy(arr, originArr)

	SelectionSort(arr)
	if judgeSort(arr) {
		fmt.Println("Selection Sort Success")
	}
	copy(arr, originArr)

	CountingSort(arr)
	if judgeSort(arr) {
		fmt.Println("Counting Sort Success")
	}
	copy(arr, originArr)

	InsertionSort(arr)
	if judgeSort(arr) {
		fmt.Println("Insertion Sort Success")
	}
	copy(arr, originArr)

	QuickSort(arr)
	if judgeSort(arr) {
		fmt.Println("Quick Sort Success")
	}
	copy(arr, originArr)

	MergeSort(arr)
	if judgeSort(arr) {
		fmt.Println("Merge Sort Success")
	}
	copy(arr, originArr)

	HeapSort(arr)
	if judgeSort(arr) {
		fmt.Println("Heap Sort Success")
	}
	copy(arr, originArr)

	ShellSort(arr)
	if judgeSort(arr) {
		fmt.Println("Shell Sort Success")
	}
	copy(arr, originArr)

	RadixSort(arr)
	if judgeSort(arr) {
		fmt.Println("Radix Sort Success")
	}
	copy(arr, originArr)

	BucketSort(arr)
	if judgeSort(arr) {
		fmt.Println("Bucket Sort Success")
	}
	copy(arr, originArr)
}
